#include <climits>
#include <cmath>
#include <cstdio>

long long map[101][101];
bool mark[101];
long long distance[101];

int main(int argc, char const* argv[])
{
    int n, m;
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            map[i][j] = 0;
        }
        mark[i] = false;
        distance[i] = -1;
    }

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a][b] = pow(2, i);
        map[b][a] = pow(2, i);
    }
    int start = 0;
    mark[start] = true;
    distance[start] = 0;
    int new_node = start;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            if (mark[j])
                continue;
            if (map[new_node][j] == 0)
                continue;
            if (distance[j] == -1 || distance[j] > distance[new_node] + map[new_node][j])
                distance[j] = distance[new_node] + map[new_node][j];
        }
        int min = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (mark[j])
                continue;
            if (distance[j] == -1)
                continue;
            if (distance[j] < min) {
                min = distance[j];
                new_node = j;
            }
        }
        mark[new_node] = true;
    }
    
    for (int i = 1; i < n; i++) {
        if(distance[i] > 0)
            printf("%d\n", distance[i] % 100000);
        else
            printf("-1\n");
    }
    return 0;
}